Optical codes are patterns made up of image areas having different light reflective or light emissive properties, which are typically assembled in accordance with a priori rules. The term "bar code" is sometimes used to describe certain kinds of optical codes. The optical properties and patterns of optical codes are selected to distinguish them in appearance from the background environments in which they are used. Devices for identifying or extracting data from optical codes are sometimes referred to as "optical code readers" of which bar code scanners are one type. Optical code readers are used in both fixed or portable installations in many diverse environments such as in stores for check-out services, in manufacturing locations for work flow and inventory control and in transport vehicles for tracking package handling. The optical code can be used as a rapid, generalized means of data entry, for example, by reading a target bar code from a printed listing of many bar codes. In some uses, the optical code reader is connected to a portable data processing device or a data collection and transmission device. Frequently, the optical code reader includes a handheld sensor which is manually directed at a target code.
Most conventional optical scanning systems are designed to read one-dimensional bar code symbols. The bar code is a pattern of variable-width rectangular bars separated by fixed or variable width spaces. The bars and spaces have different light reflecting characteristics. One example of a one dimensional bar code is the UPC/EAN code used to identify, for example, product inventory. An example of a two dimensional or stacked bar code is the PDF417 bar code. A description of PDF417 bar code and techniques for decoding it are disclosed in U.S. Pat. No. 5,635,697 to Shellhammer et al. and assigned to Symbol Technologies, Inc., which patent is incorporated herein by reference.
Conventional codes are known which are based on a two dimensional grid whose geometry is independent of data content. The grid may be a plane tiled by regular polygons such as squares or hexagons. Typically a black or white feature or polygon is located at each grid location.
One such two dimensional optical code known in the art is MaxiCode. A portion of a conventional MaxiCode symbol is shown in FIG. 4. MaxiCode is a matrix symbology made up of offset rows of hexagonal modules arranged around a finder pattern. A MaxiCode symbol may consist of a unique central finder pattern: up to 3 dark concentric rings and 3 included light areas, sometimes called a "bulls-eye". The central finder pattern is surrounded by an approximately square-shaped array of 33 offset rows of hexagonal modules. The 33 rows in the symbol alternate between 30 and 29 modules in width. Orientation information (rotation) is provided by 6 patterns of three modules each located adjacent to the bulls-eye. Data is carried in the presence or absence of darkened modules within the hexagonal grid. A binary encoding scheme may be used to represent information in black (low reflectivity) and white (high reflectivity). MaxiCode is described in detail in the publication "International Symbology Specification - MaxiCode", by AIM International, Inc. (hereinafter "AIM Specification").
Various optical codes including MaxiCode can be read employing imaging devices. For example an image sensor may be employed which has a two dimensional array of cells or photo sensors which correspond to image elements or pixels in a field of view of the device. Such an image sensor may be a two dimensional or area charge coupled device (CCD) and associated circuits for producing electronic signals corresponding to a two dimensional array of pixel information for a field of view. An imaging engine usable in reading MaxiCode is disclosed in U.S. patent application Ser. No. 09/096,578 filed Jun. 12, 1998, entitled IMAGING ENGINE AND METHOD FOR CODE READERS to Correa et al. which is hereby incorporated by reference. Electronic circuits in or associated with the imaging engine may be provided to decode MaxiCode.
The above-mentioned AIM Specification discloses a frequency--domain technique to decode MaxiCode. In such processes three principal MaxiCode axes, assumed to correspond to the hexagon grid, are found in two dimensional pixel data using a Fourier transform technique. Grid locations for the modules are then determined by use of inverse Fourier transform techniques. However, such techniques require computationally intensive, two dimensional transforms, which have long processing times particularly at high resolution levels preferred for accurate decoding. Moreover, such techniques may not accurately accommodate tilted or warped MaxiCode symbols.
Accordingly, it is an object of the present invention to provide a fast and efficient technique for decoding grid-based two dimensional code such as MaxiCode.
It is another object of the present invention to provide a technique for decoding grid based, two dimensional code which better tolerates tilt and/or warping of the code symbol as seen by the image sensor.
It is another object of the present invention to provide a technique for decoding MaxiCode which produces an accurate grid mapping which can better accommodate symbol grid distortion and which can take into account tilt in the plane of the MaxiCode symbol with respect to the optical axis of the image sensor.
In U.S. Pat. No. 5,637,849 to Wang et al., it has been proposed to extract data from a MaxiCode symbol using a spatial domain technique, without frequency domain transforms. The technique includes identifying two intersecting diameters of at least one traversal line having an alignment normal to the sides of the hexagonal data cells. In the case that the symbol is on a non-planar surface, Wang et al. teaches that the top row of data cells must be sampled by an angled row of pixels and, the middle row of data samples by a horizontal row of pixels and intermediate rows of data cells sampled at angles interpolated between the top angle and horizontal. Alternatively, or in addition, a normalization routine may be implemented for individual rows of data cells.
MaxiCode is a type of matrix code which lacks extensive self-synchronization such as that built into PDF417. Some variants of Data Matrix also fall into this category. To decode such types of two dimensional bar codes, a projection or interpolation based on a single line or even a few lines is not adequate and could result in module displacement.
Accordingly, it is an object of the present invention to provide more accurate techniques for mapping a code grid, particularly one which lacks extensive self-synchronization such as MaxiCode.
It is another object of the present invention to provide techniques for more accurately and efficiently decoding grid-based two dimensional codes in situations where the code symbol does not lie in a plane normal to the optical axis of the image sensor.
It is another object of the present invention to provide techniques for decoding grid-based two dimensional codes in situations where the code symbol or the image of the code symbol is progressively distorted from the nominal grid pattern on which the code is based.
These and other objects and features of the invention will be apparent from this written description and drawings.